import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-28
 * Time:8:16
 */
public class TestHeap {
    public int elem[];

    @Override
    public String toString() {
        return "TestHeap{" +
                "elem=" + Arrays.toString(elem) +
                '}';
    }

    public int useSize=0;
    public static final int DEFAULT_SIZE =10;
    public TestHeap(){
        elem=new int[DEFAULT_SIZE];
    }
    public void initElem(int []array){
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            useSize++;
        }
    }
    //创建堆
    public void createHeap(){
        for (int parent=(useSize-1-1)/2;parent>=0;parent--) {
            //
            shiftDown(parent,useSize);
        }
    }
    public void shiftDown(int parent,int len){
        int child=2*parent+1;
        if(child>len){
            return;
        }
        if(child+1<len&&elem[child]<elem[child+1]){
            child=child+1;
        }
        if(elem[child]>elem[parent]){
            int tmp=elem[child];
            elem[child]=elem[parent];
            elem[parent]=tmp;
            shiftDown(child,len);
        }
    }
    public void shiftDownRight(int parent,int len){
        int child=2*parent+1;
        //保证有左孩子
        while(child<len){
            if(child+1<len&&elem[child]<elem[child+1]){
                child=child+1;
            }
            //child下标一定是两个孩子的最大值
            if(elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    //添加元素
    public void offer(int val){
        if(isFull()){
            //扩容
            elem=Arrays.copyOf(elem,2*elem.length);
        }
        //添加元素
        elem[useSize]=val;
        useSize++;
        //重新调整为大根树，向上调整
        shiftUpRight(useSize-1);
    }
//    public void shiftUp(int child){
//        int parent=(child-1)/2;
//        //找到头了
//        if(parent<0){
//            return;
//        }
//        //
//        while(elem[child]>elem[parent]){
//            int tmp=elem[child];
//            elem[child]=elem[parent];
//            elem[parent]=tmp;
//            //需要继续向下看
//            child=parent;
//            shiftUp(child);
//        }
//        shiftDown((useSize-1-1)/2,useSize);
//        //孩子不比双亲大可以直接返回
//    }
    public void shiftUpRight(int child){
        int parent=(child-1)/2;
        //找到头了
        while (child>0){
            if(elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                //需要继续向上看
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
        //孩子不比双亲大可以直接返回
    }
    public boolean isFull(){
        if(useSize==elem.length){
            return true;
        }
        return false;
    }
    public int pop(){
        if(isEmpty()){
            throw new RuntimeException();
        }
        //不是空的->交换
        int tmp=elem[0];
        elem[0]=elem[useSize-1];
        elem[useSize-1]=tmp;
        useSize--;
        shiftDownRight(0,useSize-1-1);
        return tmp;

    }
    public boolean isEmpty(){
        return (elem.length==0);
    }

}
